home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / xearth-0.92 / scan.c < prev    next >
C/C++ Source or Header  |  1995-06-25  |  11KB  |  517 lines
  1. /*
  2.  * scan.c
  3.  * kirk johnson
  4.  * august 1993
  5.  *
  6.  * RCS $Id: scan.c,v 1.6 1994/05/23 23:03:26 tuna Exp $
  7.  *
  8.  * Copyright (C) 1989, 1990, 1993, 1994 Kirk Lauritz Johnson
  9.  *
  10.  * Parts of the source code (as marked) are:
  11.  *   Copyright (C) 1989, 1990, 1991 by Jim Frost
  12.  *   Copyright (C) 1992 by Jamie Zawinski <jwz@lucid.com>
  13.  *
  14.  * Permission to use, copy, modify, distribute, and sell this
  15.  * software and its documentation for any purpose is hereby granted
  16.  * without fee, provided that the above copyright notice appear in
  17.  * all copies and that both that copyright notice and this
  18.  * permission notice appear in supporting documentation. The author
  19.  * makes no representations about the suitability of this software
  20.  * for any purpose. It is provided "as is" without express or
  21.  * implied warranty.
  22.  *
  23.  * THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  24.  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS,
  25.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT
  26.  * OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  27.  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  28.  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  29.  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  30.  */
  31.  
  32. #include "xearth.h"
  33. #include "kljcpyrt.h"
  34.  
  35. #define MAP_DATA_SCALE  (30000)
  36.  
  37. #define XingTypeEntry (0)
  38. #define XingTypeExit  (1)
  39.  
  40. typedef struct
  41. {
  42.   int    type;
  43.   int    cidx;
  44.   double x, y;
  45.   double angle;
  46. } EdgeXing;
  47.  
  48. void       scan_map();
  49. void       scan_outline();
  50. void       scan_curves();
  51. double    *extract_curve();
  52. void       scan_along_curve();
  53. void       handle_xings();
  54. void       scan_arc();
  55. void       scan();
  56. void       get_scanbits();
  57.  
  58. double cos_view_lat;
  59. double sin_view_lat;
  60. double cos_view_lon;
  61. double sin_view_lon;
  62.  
  63. double proj_scale;
  64. double proj_xofs;
  65. double proj_yofs;
  66. double inv_proj_scale;
  67.  
  68. int     first_scan = 1;
  69. ExtArr  scanbits;
  70. ExtArr  edgexings;
  71. int     min_y, max_y;
  72. ExtArr *scanbuf;
  73.  
  74.  
  75. static int double_comp(a, b)
  76.      void *a;
  77.      void *b;
  78. {
  79.   double val_a;
  80.   double val_b;
  81.   int    rslt;
  82.  
  83.   val_a = *((double *) a);
  84.   val_b = *((double *) b);
  85.  
  86.   if (val_a < val_b)
  87.     rslt = -1;
  88.   else if (val_a > val_b)
  89.     rslt = 1;
  90.   else
  91.     rslt = 0;
  92.  
  93.   return rslt;
  94. }
  95.  
  96.  
  97. static int scanbit_comp(a, b)
  98.      void *a;
  99.      void *b;
  100. {
  101.   return (((ScanBit *) a)->y - ((ScanBit *) b)->y);
  102. }
  103.  
  104.  
  105. static int edgexing_comp(a, b)
  106.      void *a;
  107.      void *b;
  108. {
  109.   double angle_a;
  110.   double angle_b;
  111.   int    rslt;
  112.  
  113.   angle_a = ((EdgeXing *) a)->angle;
  114.   angle_b = ((EdgeXing *) b)->angle;
  115.  
  116.   if (angle_a < angle_b)
  117.     rslt = -1;
  118.   else if (angle_a > angle_b)
  119.     rslt = 1;
  120.   else
  121.     rslt = 0;
  122.  
  123.   return rslt;
  124. }
  125.  
  126.  
  127. void scan_map()
  128. {
  129.   int    i;
  130.   double inv_mag;
  131.  
  132.   cos_view_lat = cos(view_lat * (M_PI/180));
  133.   sin_view_lat = sin(view_lat * (M_PI/180));
  134.   cos_view_lon = cos(view_lon * (M_PI/180));
  135.   sin_view_lon = sin(view_lon * (M_PI/180));
  136.  
  137.   inv_mag        = 1 / view_mag;
  138.   proj_scale     = ((hght < wdth)
  139.             ? (hght / (2 * inv_mag))
  140.             : (wdth / (2 * inv_mag)));
  141.   proj_xofs      = (double) wdth / 2 + shift_x;
  142.   proj_yofs      = (double) hght / 2 + shift_y;
  143.   inv_proj_scale = 1 / proj_scale;
  144.  
  145.   /* the first time through, allocate scanbits.
  146.    * on subsequent passes, simply reset it.
  147.    */
  148.   if (first_scan)
  149.     scanbits = extarr_alloc(sizeof(ScanBit));
  150.   else
  151.     scanbits->count  = 0;
  152.  
  153.   edgexings = extarr_alloc(sizeof(EdgeXing));
  154.  
  155.   scanbuf = (ExtArr *) malloc((unsigned) sizeof(ExtArr) * hght);
  156.   assert(scanbuf != NULL);
  157.   for (i=0; i<hght; i++)
  158.     scanbuf[i] = extarr_alloc(sizeof(double));
  159.  
  160.   scan_outline();
  161.   scan_curves();
  162.  
  163.   extarr_free(edgexings);
  164.   for (i=0; i<hght; i++)
  165.     extarr_free(scanbuf[i]);
  166.   free(scanbuf);
  167.  
  168.   qsort(scanbits->body, scanbits->count, sizeof(ScanBit), scanbit_comp);
  169.  
  170.   first_scan = 0;
  171. }
  172.  
  173.  
  174. void scan_outline()
  175. {
  176.   min_y = hght;
  177.   max_y = -1;
  178.   scan_arc(1.0, 0.0, 0.0, 1.0, 0.0, 2*M_PI);
  179.   get_scanbits(64);
  180. }
  181.  
  182.  
  183. void scan_curves()
  184. {
  185.   int     i;
  186.   int     cidx;
  187.   int     npts;
  188.   int     val;
  189.   short  *raw;
  190.   double *pos;
  191.   double *prev;
  192.   double *curr;
  193.  
  194.   cidx = 0;
  195.   raw  = map_data;
  196.   while (1)
  197.   {
  198.     npts = raw[0];
  199.     if (npts == 0) break;
  200.     val  = raw[1];
  201.     raw += 2;
  202.  
  203.     pos   = extract_curve(npts, raw);
  204.     prev  = pos + (npts-1)*3;
  205.     curr  = pos;
  206.     min_y = hght;
  207.     max_y = -1;
  208.  
  209.     for (i=0; i<npts; i++)
  210.     {
  211.       scan_along_curve(prev, curr, cidx);
  212.       prev  = curr;
  213.       curr += 3;
  214.     }
  215.  
  216.     free(pos);
  217.     if (edgexings->count > 0)
  218.       handle_xings();
  219.     if (min_y <= max_y)
  220.       get_scanbits(val);
  221.  
  222.     cidx += 1;
  223.     raw  += 3*npts;
  224.   }
  225. }
  226.  
  227.  
  228. double *extract_curve(npts, data)
  229.      int    npts;
  230.      short *data;
  231. {
  232.   int     i;
  233.   double  tmp1;
  234.   double  tmp2;
  235.   double *pos;
  236.   double *rslt;
  237.  
  238.   rslt = (double *) malloc((unsigned) sizeof(double) * 3 * npts);
  239.   assert(rslt != NULL);
  240.  
  241.   pos = rslt;
  242.   for (i=0; i<npts; i++)
  243.   {
  244.     pos[0] = data[0] * (1.0/MAP_DATA_SCALE);
  245.     pos[1] = data[1] * (1.0/MAP_DATA_SCALE);
  246.     pos[2] = data[2] * (1.0/MAP_DATA_SCALE);
  247.  
  248.     tmp1 = (cos_view_lon * pos[0]) - (sin_view_lon * pos[2]);
  249.     tmp2 = (sin_view_lon * pos[0]) + (cos_view_lon * pos[2]);
  250.     pos[0] = tmp1;
  251.     pos[2] = tmp2;
  252.  
  253.     tmp1 = (cos_view_lat * pos[1]) - (sin_view_lat * pos[2]);
  254.     tmp2 = (sin_view_lat * pos[1]) + (cos_view_lat * pos[2]);
  255.     pos[1] = tmp1;
  256.     pos[2] = tmp2;
  257.  
  258.     data += 3;
  259.     pos  += 3;
  260.   }
  261.  
  262.   return rslt;
  263. }
  264.  
  265.  
  266. void scan_along_curve(prev, curr, cidx)
  267.      double *prev;
  268.      double *curr;
  269.      int     cidx;
  270. {
  271.   double    tmp;
  272.   double    extra[3];
  273.   EdgeXing *xing;
  274.  
  275.   if (prev[2] <= 0)             /* prev not visible */
  276.   {
  277.     if (curr[2] <= 0)
  278.       return;                   /* neither point visible */
  279.  
  280.     tmp = curr[2] / (curr[2] - prev[2]);
  281.     extra[0] = curr[0] - tmp * (curr[0] - prev[0]);
  282.     extra[1] = curr[1] - tmp * (curr[1] - prev[1]);
  283.     extra[2] = 0;
  284.  
  285.     tmp = sqrt(extra[0]*extra[0] + extra[1]*extra[1]);
  286.     extra[0] /= tmp;
  287.     extra[1] /= tmp;
  288.  
  289.     /* extra[] is an edge crossing (entry point) */
  290.     xing = (EdgeXing *) extarr_next(edgexings);
  291.     xing->type  = XingTypeEntry;
  292.     xing->cidx  = cidx;
  293.     xing->x     = extra[0];
  294.     xing->y     = extra[1];
  295.     xing->angle = atan2(extra[1], extra[0]);
  296.  
  297.     prev = extra;
  298.   }
  299.   else if (curr[2] <= 0)        /* curr not visible */
  300.   {
  301.     tmp = curr[2] / (curr[2] - prev[2]);
  302.     extra[0] = curr[0] - tmp * (curr[0] - prev[0]);
  303.     extra[1] = curr[1] - tmp * (curr[1] - prev[1]);
  304.     extra[2] = 0;
  305.  
  306.     tmp = sqrt(extra[0]*extra[0] + extra[1]*extra[1]);
  307.     extra[0] /= tmp;
  308.     extra[1] /= tmp;
  309.  
  310.     /* extra[] is an edge crossing (exit point) */
  311.     xing = (EdgeXing *) extarr_next(edgexings);
  312.     xing->type  = XingTypeExit;
  313.     xing->cidx  = cidx;
  314.     xing->x     = extra[0];
  315.     xing->y     = extra[1];
  316.     xing->angle = atan2(extra[1], extra[0]);
  317.  
  318.     curr = extra;
  319.   }
  320.  
  321.   scan(XPROJECT(prev[0]), YPROJECT(prev[1]),
  322.        XPROJECT(curr[0]), YPROJECT(curr[1]));
  323. }
  324.  
  325.  
  326. void handle_xings()
  327. {
  328.   int       i;
  329.   unsigned  nxings;
  330.   EdgeXing *xings;
  331.   EdgeXing *from;
  332.   EdgeXing *to;
  333.  
  334.   xings  = (EdgeXing *) edgexings->body;
  335.   nxings = edgexings->count;
  336.  
  337.   assert((nxings % 2) == 0);
  338.   qsort(xings, nxings, sizeof(EdgeXing), edgexing_comp);
  339.  
  340.   if (xings[0].type == XingTypeExit)
  341.   {
  342.     for (i=0; i<nxings; i+=2)
  343.     {
  344.       from = &(xings[i]);
  345.       to   = &(xings[i+1]);
  346.  
  347.       if ((from->type != XingTypeExit) ||
  348.       (to->type != XingTypeEntry))
  349.       {
  350.     fprintf(stderr, "%s:%d incorrect edgexing sequence ",
  351.         __FILE__, __LINE__);
  352.     fprintf(stderr, "(from->cidx %d, to->cidx %d)\n",
  353.         from->cidx, to->cidx);
  354.     exit(1);
  355.       }
  356.       scan_arc(from->x, from->y, from->angle, to->x, to->y, to->angle);
  357.     }
  358.   }
  359.   else
  360.   {
  361.     from = &(xings[nxings-1]);
  362.     to   = &(xings[0]);
  363.  
  364.     if ((from->type != XingTypeExit) ||
  365.     (to->type != XingTypeEntry) ||
  366.     (from->angle < to->angle))
  367.     {
  368.       fprintf(stderr, "%s:%d incorrect edgexing sequence ",
  369.           __FILE__, __LINE__);
  370.       fprintf(stderr, "(from->cidx %d, to->cidx %d)\n",
  371.           from->cidx, to->cidx);
  372.       exit(1);
  373.     }
  374.     scan_arc(from->x, from->y, from->angle, to->x, to->y, to->angle+2*M_PI);
  375.  
  376.     for (i=1; i<(nxings-1); i+=2)
  377.     {
  378.       from = &(xings[i]);
  379.       to   = &(xings[i+1]);
  380.  
  381.       if ((from->type != XingTypeExit) ||
  382.       (to->type != XingTypeEntry))
  383.       {
  384.     fprintf(stderr, "%s:%d incorrect edgexing sequence ",
  385.         __FILE__, __LINE__);
  386.     fprintf(stderr, "(from->cidx %d, to->cidx %d)\n",
  387.         from->cidx, to->cidx);
  388.     exit(1);
  389.       }
  390.       scan_arc(from->x, from->y, from->angle, to->x, to->y, to->angle);
  391.     }
  392.   }
  393.  
  394.   edgexings->count = 0;
  395. }
  396.  
  397.  
  398. void scan_arc(x0, y0, a0, x1, y1, a1)
  399.      double x0, y0, a0;
  400.      double x1, y1, a1;
  401. {
  402.   int    i;
  403.   int    lo, hi;
  404.   double angle, step;
  405.   double prev_x, prev_y;
  406.   double curr_x, curr_y;
  407.  
  408.   assert(a0 < a1);
  409.  
  410.   step = M_PI / 50;
  411.   lo   = ceil(a0 / step);
  412.   hi   = floor(a1 / step);
  413.  
  414.   prev_x = XPROJECT(x0);
  415.   prev_y = YPROJECT(y0);
  416.  
  417.   for (i=lo; i<=hi; i++)
  418.   {
  419.     angle  = i * step;
  420.     curr_x = XPROJECT(cos(angle));
  421.     curr_y = YPROJECT(sin(angle));
  422.     scan(prev_x, prev_y, curr_x, curr_y);
  423.  
  424.     prev_x = curr_x;
  425.     prev_y = curr_y;
  426.   }
  427.  
  428.   curr_x = XPROJECT(x1);
  429.   curr_y = YPROJECT(y1);
  430.   scan(prev_x, prev_y, curr_x, curr_y);
  431. }
  432.  
  433.  
  434. void scan(x0, y0, x1, y1)
  435.      double x0, y0;
  436.      double x1, y1;
  437. {
  438.   int    i;
  439.   int    lo_y, hi_y;
  440.   double x_value;
  441.   double x_delta;
  442.  
  443.   if (y0 < y1)
  444.   {
  445.     lo_y = ceil(y0 - 0.5);
  446.     hi_y = floor(y1 - 0.5);
  447.  
  448.     if (hi_y == (y1 - 0.5))
  449.       hi_y -= 1;
  450.   }
  451.   else
  452.   {
  453.     lo_y = ceil(y1 - 0.5);
  454.     hi_y = floor(y0 - 0.5);
  455.  
  456.     if (hi_y == (y0 - 0.5))
  457.       hi_y -= 1;
  458.   }
  459.  
  460.   if (lo_y < 0)     lo_y = 0;
  461.   if (hi_y >= hght) hi_y = hght-1;
  462.  
  463.   if (lo_y > hi_y)
  464.     return;                     /* no scan lines crossed */
  465.  
  466.   if (lo_y < min_y) min_y = lo_y;
  467.   if (hi_y > max_y) max_y = hi_y;
  468.  
  469.   x_value = x0 - (x0 - x1) * (y0 - (lo_y + 0.5)) / (y0 - y1);
  470.   x_delta = (x0 - x1) / (y0 - y1);
  471.  
  472.   for (i=lo_y; i<=hi_y; i++)
  473.   {
  474.     *((double *) extarr_next(scanbuf[i])) = x_value;
  475.     x_value += x_delta;
  476.   }
  477. }
  478.  
  479.  
  480. void get_scanbits(val)
  481.      int val;
  482. {
  483.   int      i, j;
  484.   int      lo_x, hi_x;
  485.   unsigned nvals;
  486.   double  *vals;
  487.   ScanBit *scanbit;
  488.  
  489.   for (i=min_y; i<=max_y; i++)
  490.   {
  491.     vals  = (double *) scanbuf[i]->body;
  492.     nvals = scanbuf[i]->count;
  493.     assert((nvals % 2) == 0);
  494.     qsort(vals, nvals, sizeof(double), double_comp);
  495.  
  496.     for (j=0; j<nvals; j+=2)
  497.     {
  498.       lo_x = ceil(vals[j] - 0.5);
  499.       hi_x = floor(vals[j+1] - 0.5);
  500.  
  501.       if (lo_x < 0)     lo_x = 0;
  502.       if (hi_x >= wdth) hi_x = wdth-1;
  503.  
  504.       if (lo_x <= hi_x)
  505.       {
  506.         scanbit = (ScanBit *) extarr_next(scanbits);
  507.         scanbit->y    = i;
  508.         scanbit->lo_x = lo_x;
  509.         scanbit->hi_x = hi_x;
  510.         scanbit->val  = val;
  511.       }
  512.     }
  513.  
  514.     scanbuf[i]->count = 0;
  515.   }
  516. }
  517.